# 正数的有符号右移和无符号右移一样
# 负数的有符号右移，空缺处补1，无符号补0

# 有符号整数，无符号整数
"""
    如 -4（int 类型有符号） 二进制表示为： 最高位为符号位，1代表-， 0代表正
    无符号整数，自然没有符号位，只能表示整数，当然多了一位，表示的数字范围也会大

    1000 0000 0000 0000 0000 0000 0000 0100
"""

# 位运算，都是指在计算机中的二进制表示运算。 负数表示为 补码形式
# 得出结论： 左移和符号位没有关系。符号位都都不动的
# 得出结论：正数右移和 符号无关
# 得出结论： 负数的有符号右移 高位补1， 无符号高位补0，和符号位有关
"""
    按位与(&): 同1出1，其他出0 ： 有个经典的例子，Python中计算字典的hash表，计算存储位置时，需要对hash值进行取模运算。
                                但是当取模的数字是 2的倍数时，就可以替换为 & 运算。比如 18 % 8 , 等价于 18 & (8-1)
                                因为 7 的二进制位 0111 1111  ,&7， 就只剩下后七位为1的了，自然等于取模运算
    按位或(|): 有1出1， 没1出0
    按位异或(^): 同出0， 异出1
    按位取反(~): 指将两个二进制数的每一二进位都进行取反操作， 0 换成 1 ， 1 换成0


    左移(有符号)（<<）, 有符号右移（>>）, 无符号右移（>>>）python中没有这个无符号右移运算符，默认有符号
    举例子 int(4)（都是默认有符号的）
    4: 0000 0000 0000 0000 0000 0000 0000 0100
    4 << 2, 左移2
    0000 0000 0000 0000 0000 0000 0001 0000 (右边低位空出来补0)
    = 16

    -4： 1111 1111 1111 1111 1111 1111 1111 1100
    -4 << 2, 左移 2
    1111 1111 1111 1111 1111 1111 1111 0000 
    = (补码-1 取反得到原数字) 1000 0000 0000 0000 0000 0000 0001 0000 = -16

    得出结论： 左移和符号位没有关系。符号位都都不动的。


    15： 0000 0000 0000 0000 0000 0000 0000 1111
    15 >> 2, 有符号右移2
    0000 0000 0000 0000 0000 0000 0000 0011  (右边空出补0)
    = 3
    15 >>> 2， 有符号右移2
    0000 0000 0000 0000 0000 0000 0000 0011  (右边空出补0)
    = 3
    得出结论：正数右移和 符号无关

    -15：1111 1111 1111 1111 1111 1111 1111 0001 （补码表示）
    -15>>2， 有符号右移2
    1111 1111 1111 1111 1111 1111 1111 1100  （前面空出补 1）
    = 取反加1 = -4

    -15 >>> 2 无符号右移2( 不将最高位当做符号位)
    0011 1111 1111 1111 1111 1111 1111 1100  （空缺补0）
    = 这是个很大的整数
    得出结论： 负数的有符号右移 高位补1， 无符号高位补0
    
"""


# 补码的作用：
"""
    1. 统一数字0的表示。
    2. 简化整数的加减法计算。

    补码 = 反码 + 1（正数的原码反码，补码等于本身）, 反码 = 除符号位以外，按位取反。
    在原码中0有两种表示方式：[+0]原=00000000，[-0]原=10000000。
    在反码表示中，0也有两种表示形式：[+0]反=00000000，[-0]反=11111111。
    在补码表示中，0有唯一的编码：[+0]补=00000000，[-0]补=00000000。
    补码是00000000，十进制数值为0

    在进行计算的时候，简化计算。任何形式的计算，都可以转化为加法。 比如 -5 - 6， 5 + （-6）等
    负数在计算机中以补码形式表示：
    上面两个可以转换为 [-5]补 + [-6]补 = [结果]补码   [5]补 + [-6]补 = [结果]补
    以第二个为例子：int 32位整数有符号
    
    # 第一位表示符号位
    5： 0000 0000 0000 0000 0000 0000 0000 0101
    6： 1000 0000 0000 0000 0000 0000 0000 0110

    补码：（整数不变，负数为取反加1）
    [5]补： 0000 0000 0000 0000 0000 0000 0000 0101
    [-6]补：1111 1111 1111 1111 1111 1111 1111 1010 

    那么，[5]补 + [-6]补 = [结果]补    （溢出情况不考虑）
    0000 0000 0000 0000 0000 0000 0000 0101 
    1111 1111 1111 1111 1111 1111 1111 1010  +
-------------------------------------------------
    1111 1111 1111 1111 1111 1111 1111 1111  

    补码-1再取反就得到结果为：-1
    1000 0000 0000 0000 0000 0000 0000 0001  
"""


# 有符号整数二进制规律
"""
前面提到的int有符号整形是 32位。那么还有其他形式

4 位的：最高一位表示符号位
0000    0
0001    1
0010    2
0011    3
0100    4
0101    5
0110    6
0111    7
1000    ？---> 表示负数，使用补码。 --> 减1 --> 1111 --> 1000 --> -8   有点绕， 1000表示8，但是是负数，那就是-8  

表示范围是 -2^3 -- 2^3 - 1
"""

# 位运算技巧 
"""
(1). 拿到一个数字二进制的低16位：假设数字是 n
n & 0xFFFF    FFFF代表16个1， 相&， 就是获取低16位了

(2). 对二进制的高16位进行取反：
假设 n: 0000 1010 0001 0000 1111 0010 0000 1010

n ^ 0xFFFF (异或)
    0000 1010 0001 0000 1111 0010 0000 1010
    0000 0000 0000 0000 1111 1111 1111 1111
    -------------------------------------------
    0000 1010 0001 0000 0000 1101 1111 0101   # 1. 相当于高16位不变，低16位取反

# 2. 再对整个 n 取反，就得到 高16位取反（因为低16位取反就变成原来的值了）
    ~n

总结： 这里的 0xFFFF 的作用就相当于是掩码(mask)


(3). 测试i+1位是否为1 
原理很简单。假设 n: 0000 1010 0001 0000 1111 0010 0000 1010
    测试第1位是否位1
    n & (1>>1)
    0000 1010 0001 0000 1111 0010 0000 1010
    0000 0000 0000 0000 0000 0000 0000 0001
    ------------------------------------------
                                          0  得到0 说明这一位不是1

同理测试第 i+1位是不是 0， 只需要  n & (i << i) != 0 就可以判断出来， 左移i 位， 来判断

(4). 去掉n的最后一位1
很简单，直接n & n - 1 即可

(5). 获取最后一位 1：
    n & -n
    n & ~(n-1)
    n^(n&(n-1))

(6) A的位减去 B的位： A & ~B
就是 全部化为二进制相减。 对应的位相减，没有进位，借位。 
        1 - 1 = 0
        0 - 1 = 0
        1 - 0 = 1
        0 - 0 = 0
    
(7) ^ 的用法技巧
a ^ 0 = a    作用： 可以统计列表中只出现一次的元素（其他元素出现两次）
a ^ a = 0
# 满足交换律（数字逻辑电路~~~学过这样的题去化简）
a ^ b ^ c = a ^ c ^ b

a ^ b 也相当于是 二进制 a + b 但是没有进位的那种

(8)统计数字n中 1的个数（二进制）
 观察这个运算：n & (n - 1)，其运算结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果
count = 0
while temp != 0:
    temp &= temp - 1
    count += 1

"""
